package practice.Day7;

import java.util.Stack;

/**
 * @Author quan
 * @Description 合法括号序列判断：自己写的只通过50%
 * @Date 2023/5/14 19:49
 */
public class Num2_LegalString {
    public static void main(String[] args) {
        String str = "()))))()(d";
        int n = 6;
        System.out.println(chkParenthesis(str, n));
    }
    //自己写的：不断找反例的过程（50%的通过率）
   /* public static boolean chkParenthesis(String str, int n) {
        int i = 0;
        int j = str.length()-1;
        while (i<=j){
            if(str.charAt(i)=='('){
                if(str.charAt(j)!=')'){
                    return false;
                }
                i++;
                j--;
            }
            else if(str.charAt(i)==')'){
                if(str.charAt(j)!='('){
                    return false;
                }
                i++;
                j--;
            }else {
                return false;
            }
        }
        return true;
    }*/

    /**
     * 答案：1、用栈这个数据结构
     * 2、不断找反例：（1）如果字符串的长度为奇数，直接false
     * (2)如果为偶数：如果字符为左括号，就入栈，如果括号为）就将栈中的左括号弹出来一个。
     * 如果取出来的字符既不是左括号也不是右括号，就false。
     * 3、最后判断栈是否为空，如果为空，就true，否则false。
     * @param str
     * @param n
     * @return
     */
    public static boolean chkParenthesis(String str, int n) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if(str.length() %2 ==1){
                return false;
            }else{
                if(c == '('){
                    stack.push(c);
                    //注意这里弹出的时候，栈不能为空
                }else if(c == ')' && !stack.isEmpty()){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
